home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / digital marsC compier / dm / stl / pthread_alloc < prev    next >
Encoding:
Text File  |  2000-06-08  |  15.8 KB  |  496 lines
  1. /*
  2.  * Copyright (c) 1996
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  */
  13.  
  14. #ifndef __SGI_STL_PTHREAD_ALLOC
  15. #define __SGI_STL_PTHREAD_ALLOC
  16.  
  17. // Pthread-specific node allocator.
  18. // This is similar to the default allocator, except that free-list
  19. // information is kept separately for each thread, avoiding locking.
  20. // This should be reasonably fast even in the presence of threads.
  21. // The down side is that storage may not be well-utilized.
  22. // It is not an error to allocate memory in thread A and deallocate
  23. // it in thread B.  But this effectively transfers ownership of the memory,
  24. // so that it can only be reallocated by thread B.  Thus this can effectively
  25. // result in a storage leak if it's done on a regular basis.
  26. // It can also result in frequent sharing of
  27. // cache lines among processors, with potentially serious performance
  28. // consequences.
  29.  
  30. #include <errno.h>
  31. #include <stl_config.h>
  32. #include <stl_alloc.h>
  33. #ifndef __RESTRICT
  34. #  define __RESTRICT
  35. #endif
  36.  
  37. #ifndef __STL_NO_BAD_ALLOC
  38. #  include <new>
  39. #endif
  40.  
  41. __STL_BEGIN_NAMESPACE
  42.  
  43. #define __STL_DATA_ALIGNMENT 8
  44.  
  45. union _Pthread_alloc_obj {
  46.     union _Pthread_alloc_obj * __free_list_link;
  47.     char __client_data[__STL_DATA_ALIGNMENT];    /* The client sees this.    */
  48. };
  49.  
  50. // Pthread allocators don't appear to the client to have meaningful
  51. // instances.  We do in fact need to associate some state with each
  52. // thread.  That state is represented by
  53. // _Pthread_alloc_per_thread_state<_Max_size>.
  54.  
  55. template<size_t _Max_size>
  56. struct _Pthread_alloc_per_thread_state {
  57.   typedef _Pthread_alloc_obj __obj;
  58.   enum { _S_NFREELISTS = _Max_size/__STL_DATA_ALIGNMENT };
  59.   _Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS]; 
  60.   _Pthread_alloc_per_thread_state<_Max_size> * __next; 
  61.     // Free list link for list of available per thread structures.
  62.       // When one of these becomes available for reuse due to thread
  63.     // termination, any objects in its free list remain associated
  64.     // with it.  The whole structure may then be used by a newly
  65.     // created thread.
  66.   _Pthread_alloc_per_thread_state() : __next(0)
  67.   {
  68.     memset((void *)__free_list, 0, (size_t) _S_NFREELISTS * sizeof(__obj *));
  69.   }
  70.   // Returns an object of size __n, and possibly adds to size n free list.
  71.   void *_M_refill(size_t __n);
  72. };
  73.  
  74. // Pthread-specific allocator.
  75. // The argument specifies the largest object size allocated from per-thread
  76. // free lists.  Larger objects are allocated using malloc_alloc.
  77. // Max_size must be a power of 2.
  78. template <size_t _Max_size = 128>
  79. class _Pthread_alloc_template {
  80.  
  81. public: // but only for internal use:
  82.  
  83.   typedef _Pthread_alloc_obj __obj;
  84.  
  85.   // Allocates a chunk for nobjs of size size.  nobjs may be reduced
  86.   // if it is inconvenient to allocate the requested number.
  87.   static char *_S_chunk_alloc(size_t __size, int &__nobjs);
  88.  
  89.   enum {_S_ALIGN = __STL_DATA_ALIGNMENT};
  90.  
  91.   static size_t _S_round_up(size_t __bytes) {
  92.         return (((__bytes) + (int) _S_ALIGN-1) & ~((int) _S_ALIGN - 1));
  93.   }
  94.   static size_t _S_freelist_index(size_t __bytes) {
  95.         return (((__bytes) + (int) _S_ALIGN-1)/(int)_S_ALIGN - 1);
  96.   }
  97.  
  98. private:
  99.   // Chunk allocation state. And other shared state.
  100.   // Protected by _S_chunk_allocator_lock.
  101.   static pthread_mutex_t _S_chunk_allocator_lock;
  102.   static char *_S_start_free;
  103.   static char *_S_end_free;
  104.   static size_t _S_heap_size;
  105.   static _Pthread_alloc_per_thread_state<_Max_size>* _S_free_per_thread_states;
  106.   static pthread_key_t _S_key;
  107.   static bool _S_key_initialized;
  108.         // Pthread key under which per thread state is stored. 
  109.         // Allocator instances that are currently unclaimed by any thread.
  110.   static void _S_destructor(void *instance);
  111.         // Function to be called on thread exit to reclaim per thread
  112.         // state.
  113.   static _Pthread_alloc_per_thread_state<_Max_size> *_S_new_per_thread_state();
  114.         // Return a recycled or new per thread state.
  115.   static _Pthread_alloc_per_thread_state<_Max_size> *_S_get_per_thread_state();
  116.         // ensure that the current thread has an associated
  117.         // per thread state.
  118.   class _M_lock;
  119.   friend class _M_lock;
  120.   class _M_lock {
  121.       public:
  122.         _M_lock () { pthread_mutex_lock(&_S_chunk_allocator_lock); }
  123.         ~_M_lock () { pthread_mutex_unlock(&_S_chunk_allocator_lock); }
  124.   };
  125.  
  126. public:
  127.  
  128.   /* n must be > 0      */
  129.   static void * allocate(size_t __n)
  130.   {
  131.     __obj * volatile * __my_free_list;
  132.     __obj * __RESTRICT __result;
  133.     _Pthread_alloc_per_thread_state<_Max_size>* __a;
  134.  
  135.     if (__n > _Max_size) {
  136.         return(malloc_alloc::allocate(__n));
  137.     }
  138.     if (!_S_key_initialized ||
  139.         !(__a = (_Pthread_alloc_per_thread_state<_Max_size>*)
  140.                                  pthread_getspecific(_S_key))) {
  141.         __a = _S_get_per_thread_state();
  142.     }
  143.     __my_free_list = __a -> __free_list + _S_freelist_index(__n);
  144.     __result = *__my_free_list;
  145.     if (__result == 0) {
  146.         void *__r = __a -> _M_refill(_S_round_up(__n));
  147.         return __r;
  148.     }
  149.     *__my_free_list = __result -> __free_list_link;
  150.     return (__result);
  151.   };
  152.  
  153.   /* p may not be 0 */
  154.   static void deallocate(void *__p, size_t __n)
  155.   {
  156.     __obj *__q = (__obj *)__p;
  157.     __obj * volatile * __my_free_list;
  158.     _Pthread_alloc_per_thread_state<_Max_size>* __a;
  159.  
  160.     if (__n > _Max_size) {
  161.         malloc_alloc::deallocate(__p, __n);
  162.         return;
  163.     }
  164.     if (!_S_key_initialized ||
  165.         !(__a = (_Pthread_alloc_per_thread_state<_Max_size> *)
  166.                 pthread_getspecific(_S_key))) {
  167.         __a = _S_get_per_thread_state();
  168.     }
  169.     __my_free_list = __a->__free_list + _S_freelist_index(__n);
  170.     __q -> __free_list_link = *__my_free_list;
  171.     *__my_free_list = __q;
  172.   }
  173.  
  174.   static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz);
  175.  
  176. } ;
  177.  
  178. typedef _Pthread_alloc_template<> pthread_alloc;
  179.  
  180.  
  181. template <size_t _Max_size>
  182. void _Pthread_alloc_template<_Max_size>::_S_destructor(void * __instance)
  183. {
  184.     _M_lock __lock_instance;    // Need to acquire lock here.
  185.     _Pthread_alloc_per_thread_state<_Max_size>* __s =
  186.         (_Pthread_alloc_per_thread_state<_Max_size> *)__instance;
  187.     __s -> __next = _S_free_per_thread_states;
  188.     _S_free_per_thread_states = __s;
  189. }
  190.  
  191. template <size_t _Max_size>
  192. _Pthread_alloc_per_thread_state<_Max_size> *
  193. _Pthread_alloc_template<_Max_size>::_S_new_per_thread_state()
  194. {    
  195.     /* lock already held here.    */
  196.     if (0 != _S_free_per_thread_states) {
  197.         _Pthread_alloc_per_thread_state<_Max_size> *__result =
  198.                     _S_free_per_thread_states;
  199.         _S_free_per_thread_states = _S_free_per_thread_states -> __next;
  200.         return __result;
  201.     } else {
  202.         return new _Pthread_alloc_per_thread_state<_Max_size>;
  203.     }
  204. }
  205.  
  206. template <size_t _Max_size>
  207. _Pthread_alloc_per_thread_state<_Max_size> *
  208. _Pthread_alloc_template<_Max_size>::_S_get_per_thread_state()
  209. {
  210.     /*REFERENCED*/
  211.     _M_lock __lock_instance;    // Need to acquire lock here.
  212.     int __ret_code;
  213.     _Pthread_alloc_per_thread_state<_Max_size> * __result;
  214.     if (!_S_key_initialized) {
  215.         if (pthread_key_create(&_S_key, _S_destructor)) {
  216.         __THROW_BAD_ALLOC;  // defined in stl_alloc.h
  217.         }
  218.         _S_key_initialized = true;
  219.     }
  220.     __result = _S_new_per_thread_state();
  221.     __ret_code = pthread_setspecific(_S_key, __result);
  222.     if (__ret_code) {
  223.       if (__ret_code == ENOMEM) {
  224.     __THROW_BAD_ALLOC;
  225.       } else {
  226.     // EINVAL
  227.     abort();
  228.       }
  229.     }
  230.     return __result;
  231. }
  232.  
  233. /* We allocate memory in large chunks in order to avoid fragmenting     */
  234. /* the malloc heap too much.                                            */
  235. /* We assume that size is properly aligned.                             */
  236. template <size_t _Max_size>
  237. char *_Pthread_alloc_template<_Max_size>
  238. ::_S_chunk_alloc(size_t __size, int &__nobjs)
  239. {
  240.   {
  241.     char * __result;
  242.     size_t __total_bytes;
  243.     size_t __bytes_left;
  244.     /*REFERENCED*/
  245.     _M_lock __lock_instance;         // Acquire lock for this routine
  246.  
  247.     __total_bytes = __size * __nobjs;
  248.     __bytes_left = _S_end_free - _S_start_free;
  249.     if (__bytes_left >= __total_bytes) {
  250.         __result = _S_start_free;
  251.         _S_start_free += __total_bytes;
  252.         return(__result);
  253.     } else if (__bytes_left >= __size) {
  254.         __nobjs = __bytes_left/__size;
  255.         __total_bytes = __size * __nobjs;
  256.         __result = _S_start_free;
  257.         _S_start_free += __total_bytes;
  258.         return(__result);
  259.     } else {
  260.         size_t __bytes_to_get =
  261.         2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
  262.         // Try to make use of the left-over piece.
  263.         if (__bytes_left > 0) {
  264.             _Pthread_alloc_per_thread_state<_Max_size>* __a = 
  265.                 (_Pthread_alloc_per_thread_state<_Max_size>*)
  266.             pthread_getspecific(_S_key);
  267.             __obj * volatile * __my_free_list =
  268.                         __a->__free_list + _S_freelist_index(__bytes_left);
  269.  
  270.             ((__obj *)_S_start_free) -> __free_list_link = *__my_free_list;
  271.             *__my_free_list = (__obj *)_S_start_free;
  272.         }
  273. #       ifdef _SGI_SOURCE
  274.           // Try to get memory that's aligned on something like a
  275.           // cache line boundary, so as to avoid parceling out
  276.           // parts of the same line to different threads and thus
  277.           // possibly different processors.
  278.           {
  279.             const int __cache_line_size = 128;  // probable upper bound
  280.             __bytes_to_get &= ~(__cache_line_size-1);
  281.             _S_start_free = (char *)memalign(__cache_line_size, __bytes_to_get); 
  282.             if (0 == _S_start_free) {
  283.               _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
  284.             }
  285.           }
  286. #       else  /* !SGI_SOURCE */
  287.           _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
  288. #       endif
  289.         _S_heap_size += __bytes_to_get;
  290.         _S_end_free = _S_start_free + __bytes_to_get;
  291.     }
  292.   }
  293.   // lock is released here
  294.   return(_S_chunk_alloc(__size, __nobjs));
  295. }
  296.  
  297.  
  298. /* Returns an object of size n, and optionally adds to size n free list.*/
  299. /* We assume that n is properly aligned.                                */
  300. /* We hold the allocation lock.                                         */
  301. template <size_t _Max_size>
  302. void *_Pthread_alloc_per_thread_state<_Max_size>
  303. ::_M_refill(size_t __n)
  304. {
  305.     int __nobjs = 128;
  306.     char * __chunk =
  307.     _Pthread_alloc_template<_Max_size>::_S_chunk_alloc(__n, __nobjs);
  308.     __obj * volatile * __my_free_list;
  309.     __obj * __result;
  310.     __obj * __current_obj, * __next_obj;
  311.     int __i;
  312.  
  313.     if (1 == __nobjs)  {
  314.         return(__chunk);
  315.     }
  316.     __my_free_list = __free_list
  317.          + _Pthread_alloc_template<_Max_size>::_S_freelist_index(__n);
  318.  
  319.     /* Build free list in chunk */
  320.       __result = (__obj *)__chunk;
  321.       *__my_free_list = __next_obj = (__obj *)(__chunk + __n);
  322.       for (__i = 1; ; __i++) {
  323.         __current_obj = __next_obj;
  324.         __next_obj = (__obj *)((char *)__next_obj + __n);
  325.         if (__nobjs - 1 == __i) {
  326.             __current_obj -> __free_list_link = 0;
  327.             break;
  328.         } else {
  329.             __current_obj -> __free_list_link = __next_obj;
  330.         }
  331.       }
  332.     return(__result);
  333. }
  334.  
  335. template <size_t _Max_size>
  336. void *_Pthread_alloc_template<_Max_size>
  337. ::reallocate(void *__p, size_t __old_sz, size_t __new_sz)
  338. {
  339.     void * __result;
  340.     size_t __copy_sz;
  341.  
  342.     if (__old_sz > _Max_size
  343.     && __new_sz > _Max_size) {
  344.         return(realloc(__p, __new_sz));
  345.     }
  346.     if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
  347.     __result = allocate(__new_sz);
  348.     __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
  349.     memcpy(__result, __p, __copy_sz);
  350.     deallocate(__p, __old_sz);
  351.     return(__result);
  352. }
  353.  
  354. template <size_t _Max_size>
  355. _Pthread_alloc_per_thread_state<_Max_size> *
  356. _Pthread_alloc_template<_Max_size>::_S_free_per_thread_states = 0;
  357.  
  358. template <size_t _Max_size>
  359. pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key;
  360.  
  361. template <size_t _Max_size>
  362. bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false;
  363.  
  364. template <size_t _Max_size>
  365. pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock
  366. = PTHREAD_MUTEX_INITIALIZER;
  367.  
  368. template <size_t _Max_size>
  369. char *_Pthread_alloc_template<_Max_size>
  370. ::_S_start_free = 0;
  371.  
  372. template <size_t _Max_size>
  373. char *_Pthread_alloc_template<_Max_size>
  374. ::_S_end_free = 0;
  375.  
  376. template <size_t _Max_size>
  377. size_t _Pthread_alloc_template<_Max_size>
  378. ::_S_heap_size = 0;
  379.  
  380. #ifdef __STL_USE_STD_ALLOCATORS
  381.  
  382. template <class _Tp>
  383. class pthread_allocator {
  384.   typedef pthread_alloc _S_Alloc;          // The underlying allocator.
  385. public:
  386.   typedef size_t     size_type;
  387.   typedef ptrdiff_t  difference_type;
  388.   typedef _Tp*       pointer;
  389.   typedef const _Tp* const_pointer;
  390.   typedef _Tp&       reference;
  391.   typedef const _Tp& const_reference;
  392.   typedef _Tp        value_type;
  393.  
  394.   template <class _NewType> struct rebind {
  395.     typedef pthread_allocator<_NewType> other;
  396.   };
  397.  
  398.   pthread_allocator() __STL_NOTHROW {}
  399.   pthread_allocator(const pthread_allocator& a) __STL_NOTHROW {}
  400.   template <class _OtherType>
  401.     pthread_allocator(const pthread_allocator<_OtherType>&)
  402.         __STL_NOTHROW {}
  403.   ~pthread_allocator() __STL_NOTHROW {}
  404.  
  405.   pointer address(reference __x) const { return &__x; }
  406.   const_pointer address(const_reference __x) const { return &__x; }
  407.  
  408.   // __n is permitted to be 0.  The C++ standard says nothing about what
  409.   // the return value is when __n == 0.
  410.   _Tp* allocate(size_type __n, const void* = 0) {
  411.     return __n != 0 ? static_cast<_Tp*>(_S_Alloc::allocate(__n * sizeof(_Tp)))
  412.                     : 0;
  413.   }
  414.  
  415.   // p is not permitted to be a null pointer.
  416.   void deallocate(pointer __p, size_type __n)
  417.     { _S_Alloc::deallocate(__p, __n * sizeof(_Tp)); }
  418.  
  419.   size_type max_size() const __STL_NOTHROW 
  420.     { return size_t(-1) / sizeof(_Tp); }
  421.  
  422.   void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
  423.   void destroy(pointer _p) { _p->~_Tp(); }
  424. };
  425.  
  426. template<>
  427. class pthread_allocator<void> {
  428. public:
  429.   typedef size_t      size_type;
  430.   typedef ptrdiff_t   difference_type;
  431.   typedef void*       pointer;
  432.   typedef const void* const_pointer;
  433.   typedef void        value_type;
  434.  
  435.   template <class _NewType> struct rebind {
  436.     typedef pthread_allocator<_NewType> other;
  437.   };
  438. };
  439.  
  440. template <size_t _Max_size>
  441. inline bool operator==(const _Pthread_alloc_template<_Max_size>&,
  442.                        const _Pthread_alloc_template<_Max_size>&)
  443. {
  444.   return true;
  445. }
  446.  
  447. template <class _T1, class _T2>
  448. inline bool operator==(const pthread_allocator<_T1>&,
  449.                        const pthread_allocator<_T2>& a2) 
  450. {
  451.   return true;
  452. }
  453.  
  454. template <class _T1, class _T2>
  455. inline bool operator!=(const pthread_allocator<_T1>&,
  456.                        const pthread_allocator<_T2>&)
  457. {
  458.   return false;
  459. }
  460.  
  461. template <class _Tp, size_t _Max_size>
  462. struct _Alloc_traits<_Tp, _Pthread_alloc_template<_Max_size> >
  463. {
  464.   static const bool _S_instanceless = true;
  465.   typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max_size> > _Alloc_type;
  466.   typedef __allocator<_Tp, _Pthread_alloc_template<_Max_size> > 
  467.           allocator_type;
  468. };
  469.  
  470. template <class _Tp, class _Atype, size_t _Max>
  471. struct _Alloc_traits<_Tp, __allocator<_Atype, _Pthread_alloc_template<_Max> > >
  472. {
  473.   static const bool _S_instanceless = true;
  474.   typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max> > _Alloc_type;
  475.   typedef __allocator<_Tp, _Pthread_alloc_template<_Max> > allocator_type;
  476. };
  477.  
  478. template <class _Tp, class _Atype>
  479. struct _Alloc_traits<_Tp, pthread_allocator<_Atype> >
  480. {
  481.   static const bool _S_instanceless = true;
  482.   typedef simple_alloc<_Tp, _Pthread_alloc_template<> > _Alloc_type;
  483.   typedef pthread_allocator<_Tp> allocator_type;
  484. };
  485.  
  486.  
  487. #endif /* __STL_USE_STD_ALLOCATORS */
  488.  
  489. __STL_END_NAMESPACE
  490.  
  491. #endif /* __SGI_STL_PTHREAD_ALLOC */
  492.  
  493. // Local Variables:
  494. // mode:C++
  495. // End:
  496.